package algorithms.a08MinimumSpanTrees;

import algorithms.a04heap.MinHeap;
import algorithms.a06unionfind.UnionFind4;
import com.google.common.collect.Sets;

import java.net.URI;
import java.util.Iterator;
import java.util.Set;

/**
 * Kruskal最小生成树算法
 *
 * @author 王昊然
 * @create 2018-03-09 9:08
 **/
public class KruskalMST<Weight extends Number & Comparable> {

    private Set<Edge<Weight>> edges;//最小生成树的边集合
    private Number weightMST;

    public KruskalMST(WeightedGraph<Weight> g) {

        edges = Sets.newHashSet();
        MinHeap<Edge> mh = new MinHeap<Edge>(g.E());
        weightMST = 0;

        for (int i = 0; i < g.V(); i++) {
            Iterator<Edge> iterator = g.adj(i).iterator();
            while (iterator.hasNext()) {
                Edge e = iterator.next();
                if(e.W()<=e.V()){//可同时满足有向图、无向图、自指定边
                    mh.insert(e);
                }
            }
        }

        UnionFind4 uf = new UnionFind4(g.V());

        while (!mh.isEmpty() && edges.size() < g.V() - 1) {
            Edge minE = mh.extractMin();
            if (!uf.isConnected(minE.V(), minE.W())) {
                edges.add(minE);
                uf.unionElements(minE.V(), minE.W());
            }
        }

        Iterator<Edge<Weight>> iterator = edges.iterator();
        while (iterator.hasNext())
            weightMST = weightMST.doubleValue() + iterator.next().wt().doubleValue();
    }

    // 返回最小生成树的所有边
    public Set<Edge<Weight>> mstEdges(){
        return edges;
    }

    // 返回最小生成树的权值
    Number result(){
        return weightMST;
    }

    // 测试 Kruskal
    public static void main(String[] args) throws Exception{

        URI fileUri = KruskalMST.class.getResource("testG1.txt").toURI();
        int V = 8;

        SparseWeightedGraph<Double> g = new SparseWeightedGraph<Double>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, fileUri);

        // Test Kruskal
        System.out.println("Test Kruskal:");
        KruskalMST<Double> kruskalMST = new KruskalMST<Double>(g);
        Set<Edge<Double>> mst = kruskalMST.mstEdges();
        Iterator<Edge<Double>> iterator = mst.iterator();
        while(iterator.hasNext() )
            System.out.println(iterator.next());
        System.out.println("The MST weight is: " + kruskalMST.result());
    }

}
